package Algorithm.search;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置 https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
 * 题目简述：在一个非递减数组中寻找一个值的起始位置和终止位置，不存在则返回[-1,-1]
 */
public class SearchRange {

    public static void main(String[] args) {
        new SearchRange().searchRange(new int[]{1}, 1);
    }

    /**
     * 思路：起始位置i即target-1的插入位置，终止位置j即target的插入位置-1。若target不存在则i必定大于j
     */
    public int[] searchRange(int[] nums, int target) {
        int i = searchInsert2(nums, target-1);
        int j = searchInsert2(nums, target) - 1;
        return i <= j ? new int[]{i, j} : new int[]{-1, -1};
    }

    /**
     * 寻找目标值的插入位置，当存在重复值时插入到它们后面
     */
    public int searchInsert2(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            //循环不变量：[0, low)：小于等于target的元素，(high, length-1]：大于target的元素
            if (nums[mid] <= target) low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }
}
